#include "main/utils.h"
#include "lib/list.h"
using namespace std;

ListNode* findInterNode(ListNode* head) {
  auto fast_node = head;
  auto slow_node = head;
  while (fast_node) {
    fast_node = fast_node->next;
    if (fast_node) {
      fast_node = fast_node->next;
    }
    if (fast_node)
      slow_node = slow_node->next;
  }
  auto ret = slow_node->next;
  slow_node->next = nullptr;
  return ret;
}

ListNode* reverseList(ListNode* head) {
  if (head == nullptr)
    return nullptr;

  ListNode* pre_node = nullptr;
  ListNode* cur_node = head;
  ListNode* tail_node = head;
  while (cur_node) {
    auto next_node = cur_node->next;
    if (!next_node) {
      tail_node = cur_node;
    }
    cur_node->next = pre_node;
    pre_node = cur_node;
    cur_node = next_node;
  }
  return tail_node;
}

bool isPalindrome(ListNode* head) {
  auto inter_node = findInterNode(head);
  auto reverse_node = reverseList(inter_node);
  PrintList(head);
  PrintList(reverse_node);
  while (head && reverse_node) {
    if (head->value != reverse_node->value) {
      return false;
    }
    head = head->next;
    reverse_node = reverse_node->next;
  }
  return true;
}

int main() {
  vector<int> vec = {1, 2, 3, 4, 3, 2, 1};
  ListNode* head = CreateList(vec);
  bool ret = isPalindrome(head);
  cout << ret << endl;

  return 0;
}
